package search.binary_search;

/**
 * 二分查找 时间复杂度0(logN)
 * <p>
 * 注意事项：
 * 1.循环退出条件 low<=high 不是<
 * 2.求中间值的时候先加再除以二可能会溢出
 * 3.low和high的更新如果没，没减一可能会死循环
 * <p>
 * 应用场景：
 * 1.依赖顺序存储即数组
 * 2.数据必须有序
 * 3.数据量太小不适合
 * 4.数据量太大不适合，因为数组需要连续的存储空间
 *
 * @author yeyangtao created at 11:36 2020/9/29
 */
public class BinarySearch {
    public static int binarySearch(int[] a, int value) {
        int size = a.length;
        int low = 0;
        int high = size - 1;
        while (low <= high) {
            //(low + high) >> 1 容易溢出
            int mid = low + ((high - low) >> 1);
            if (a[mid] == value) return mid;
            else if (a[mid] > value)
                high = mid - 1;
            else low = mid + 1;
        }
        return -1;
    }
}
